51nod1242 斐波那契数列 矩阵快速幂

发表于 | 分类于 |

斐波那契数列的定义如下：

F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2) (n >= 2)

(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …)
给出n，求F(n)，由于结果很大，输出F(n) % 1000000009的结果即可。

Input
输入1个数n(1 <= n <= 10^18)。
Output
输出F(n) % 1000000009的结果。
Input示例
11
Output示例
89

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<stdio.h>
#define mod 1000000009
 struct node{
    long long int c[2][2];
} t;
long long int n;
node mul(node a,node b){//矩阵乘法
    node c;
    int i,j,k;
    for(i=0;i<2;i++){
        for(j=0;j<2;j++){
            c.c[i][j]=0;
            for(k=0;k<2;k++)
                c.c[i][j]+=(a.c[i][k]*b.c[k][j])%mod;
        c.c[i][j]=c.c[i][j]%mod;
        }
    }
    return c;
}
node kuaisumi(long long int n){
   node res = t;
    if(n<0)
        return res;
    while(n){
        if(n&1)
            res=mul(res,t);
        t=mul(t,t);
        n=n>>1;
    }
    return res;
}
int main(){
    while(~scanf("%lld",&n)){
        t.c[0][0] = 1;
        t.c[0][1] = 1;
        t.c[1][0] = 1;
        t.c[1][1] = 0;
        node res=kuaisumi(n-2);
        printf("%lld\n",res.c[0][0]);
    }
}